package com.leo.datastruct.sort;

/**
 * 构建大顶堆，然后将最大值交换到末尾
 * @author xuexiaolei
 * @version 2018年02月02日
 */
public class HeapSort extends Sortable {

    public HeapSort(String sortMethodName) {
        super(sortMethodName);
    }

    @Override
    public void sort(int[] s) {
        //构建大顶堆
        for (int i = s.length/2; i >= 0 ; i--) {
            heapAdjust(s, i, s.length);
        }
        //逐步将每个最大值的根节点与末尾元素交换，并且再调整二叉树，使其成为大顶堆
        for (int i = s.length-1; i >0 ; i--) {
            swap(s, 0, i);     //将堆顶记录和当前未经排序子序列的最后一个记录交换
            heapAdjust(s, 0, i);//交换之后，需要重新检查堆是否符合大顶堆，不符合则要调整
        }
    }

    /**
     * 调整堆节点
     * @param s 操作数组
     * @param i 要调整的节点
     * @param n 数组的长度限制，不包含n
     */
    private void heapAdjust(int[] s, int i, int n){
        int child;
        int father = i;
        while (leftChild(father) < n){
            child = leftChild(father);

            //如果右孩子比较大的话，那就父节点直接和右孩子比较就行了
            if (child+1 < n && s[child+1] > s[child]){
                child++;
            }

            if (s[father] > s[child]){
                //不需要调整，也就不需要继续向下调整了
                break;
            }else {
                swap(s, father, child);
            }
            father = child;
        }

    }

    /**
     * 获取节点的左孩子
     * @param i
     * @return
     */
    private int leftChild(int i){
        return 2*i+1;
    }


    public static void main(String[] args) {
        Sortable a = new HeapSort("堆排序");
        a.testSort(new int[]{49,38,65,97,76,13,27,49,78,34,12,64,1});
    }
}
